package com.xy6.algo.force;

import java.util.Arrays;

/**
 * 蛮力法求解旅行商问题(Traveling Salesman Problem)
 * 
 * <pre>
 * 有若干个城市，任何两个城市之间的距离都是确定的，
 * 现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的城市，
 * 问如何事先确定一条最短的线路已保证其旅行的费用最少？
 * </pre>
 * 
 * @author zhang
 * @since 2018-01-06
 */
public class TSP {

	public static void main(String[] args) {
		// 城市到城市之间的距离
		int[][] d = { { 0, 10, 20, 30 }, { 11, 0, 21, 31 }, { 12, 22, 0, 32 }, { 13, 23, 33, 0 } };
		// 起点城市
		int s = 0;
		TSP tsp = new TSP();
		System.out.println(tsp.calc(s,d));
	}
	
	/**
	 * 全排列个数记录
	 */
	private int count = 0;

	/**
	 * 全排列求解旅行商问题
	 * 
	 * @param d
	 */
	public int calc(int s, int[][] cost) {
		int n = cost.length;
		// 计算n-1个数的全排列。保证值不相同
		int[] full = new int[n - 1];
		int j = 0;
		for (int i = 0; i < n; i++) {
			if (i == s) {
				continue;
			}
			full[j++] = i;
		}
		int[] arr = new int[n-1];
		// 计算全排列总数
		int rangeNum = calc(n-1);
		int[][] fullRange = new int[rangeNum][];
		
		this.fullSort(full, arr, 0, fullRange);
		
		int min = -1;
		int temp;
		int[] tempArr = new int[n - 1];
		for (int i = 0; i < fullRange.length; i++) {
			temp = calcCost(fullRange[i], cost, s);
//			System.out.println(String.format("%s, %d", Arrays.toString(fullRange[i]), temp));
			if(min == -1 || temp < min){
				min = temp;
				tempArr = fullRange[i];
			}
		}
		System.out.println(Arrays.toString(tempArr));
		
		return min;
	}
	
	
	/**
	 * 计算n的阶乘
	 * 
	 * @param n
	 * @return
	 */
	private static int calc(int n){
		int total = 1;
		for(int i=1; i<=n; i++){
			total = total * i;
		}
		return total;
	}
	
	/**
	 * 递归输出全排列各序列，将序列保存到一个集合中
	 * 
	 * @param full
	 * @param arr
	 * @param idx
	 * @param count
	 * @param fullRange
	 */
	private void fullSort(int[] full, int[] arr, int idx, int[][] fullRange){
		if(idx >= full.length){
			return;
		}
		for(int i=0; i<full.length; i++){
			boolean exist = false;
			for (int j = 0; j < idx; j++) {
				if(full[i] == arr[j]){
					exist = true;
					break;
				}
			}
			if(exist){
				continue;
			}
			arr[idx] = full[i];
			if(idx == full.length - 1){
				// 逐个复制元素，避免引用传递
				fullRange[count] = new int[arr.length];
				for (int k = 0; k < arr.length; k++) {
					fullRange[count][k] = arr[k];
				}
				count++;
			}
			fullSort(full, arr, idx + 1, fullRange);
		}
	}
	
	/**
	 * 按照某个路线旅行时，计算总费用
	 * 
	 * @param persons
	 * @param cost
	 * @return
	 */
	private static int calcCost(int[] places, int[][] cost, int s){
		int total = 0;
		total += cost[s][places[0]];
		for (int i = 1; i < places.length; i++) {
			total += cost[places[i-1]][places[i]];
		}
		total += cost[places[places.length - 1]][s];
		
		return total;
	}

}
